package leetcode.code2192;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

import leetcode.IDebug;

public class Solution implements IDebug {

	public List<List<Integer>> getAncestors(int n, int[][] edges) {
		int[] ins = new int[n];// 入度
		List<List<Integer>> collect = new ArrayList<>();// 收集节点
		List<Integer>[] roots = new ArrayList[n];// 直接上级
		List<Integer>[] nexts = new ArrayList[n];// 直接下级
		for (int i = 0; i < n; i++) {
			collect.add(new ArrayList<Integer>());
			roots[i] = new ArrayList<>();
			nexts[i] = new ArrayList<>();
		}
		for (int[] edge : edges) {
			int from = edge[0], to = edge[1];
			ins[to]++;
			roots[to].add(from);
			nexts[from].add(to);
		}
		Queue<Integer> queue = new LinkedList<>();// 拓扑排序，0入度根
		for (int i = 0; i < n; i++) {
			if (ins[i] == 0) {
				queue.add(i);
			}
		}
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			List<Integer> froms = roots[cur];
			Set<Integer> curAns = new HashSet<>();
			// 直接上级的答案，和直接上级，收集到curAns
			for (int from : froms) {
				List<Integer> rans = collect.get(from);
				curAns.addAll(rans);
				curAns.add(from);
			}
			// cur的未排序答案
			collect.get(cur).addAll(curAns);
			List<Integer> next = nexts[cur];
			// 消入度
			for (Integer nxt : next) {
				int in = --ins[nxt];
				if (in == 0) {
					queue.add(nxt);
				}
			}
		}
		// 拎出来排序
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			List<Integer> list = collect.get(i);
			Collections.sort(list);
			ans.add(list);
		}
		return ans;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
